package data.structures.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {

    public static void main(String[] args) {
        //进行测试
        //先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");

        HeroNode hero5 = new HeroNode(5, "孙悟空", "孙行者");
        HeroNode hero6 = new HeroNode(6, "猪八戒", "猪悟能");
        HeroNode hero7 = new HeroNode(7, "沙僧", "沙和尚");
        HeroNode hero8 = new HeroNode(8, "唐僧", "金蝉子");

        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        //加入
         singleLinkedList1.add(hero1);
        singleLinkedList1.add(hero5);
         singleLinkedList1.add(hero7);
        singleLinkedList1.add(hero2);

        singleLinkedList2.add(hero6);
        singleLinkedList2.add(hero3);
        singleLinkedList2.add(hero8);
        singleLinkedList2.add(hero4);



        //加入链表  -- 按顺序添加
/*        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero3);*/

        System.out.println("==水浒传==>");
        singleLinkedList1.list();
        System.out.println("==西游记==>");
        singleLinkedList2.list();

/*
         //修改节点
        HeroNode heroUpdate = new HeroNode(4, "林冲~~~", "豹子头~~~");
        singleLinkedList.update(heroUpdate);

        //删除节点
        //singleLinkedList.deleteList(1);
        //singleLinkedList.deleteList(3);

        singleLinkedList.list();


        //        求单链表中有效节点的个数
        int length = getLength(singleLinkedList.getHeroNode());
        System.out.println("length = " + length);


        //找单链表中的倒数第k个结点
        HeroNode lastIndexNode = findLastIndexNode(singleLinkedList.getHeroNode(), 2);
*/
        //反转链表
        // reversetList(singleLinkedList.getHeroNode());
        System.out.println("=====");
        // singleLinkedList.list();
        //从尾到头打印单链表
        // reversePrint(singleLinkedList.getHeroNode());

    }


    /**
     * 单链表的常见面试题有如下:
     * 1、求单链表中有效节点的个数
     * 2、查找单链表中的倒数第k个结点 【新浪面试题】
     * 3、单链表的反转【腾讯面试题，有点难度】
     * 4、从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】
     * 5、合并两个有序的单链表，合并之后的链表依然有序【课后练习.】
     */


    /**
     * 求单链表中有效节点的个数
     *
     * @return
     */
    public static int getLength(HeroNode node) {

        if (node.next == null) {
            return 0;
        }
        //排除头结点
        HeroNode temp = node.next;
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

    /**
     * 查找单链表中的倒数第k个结点
     *
     * @param node  头结点
     * @param index 倒数第index个
     * @return 返回节点
     */
    public static HeroNode findLastIndexNode(HeroNode node, int index) {
        if (node.next == null) {
            return null;
        }
        //遍历获得链表长度
        int length = getLength(node);
        //判断index大小
        if (index <= 0 || index > length) {
            return null;
        }
        HeroNode temp = node.next;
        //遍历链表获得length-index位置的节点数据
        for (int i = 0; i < length - index; i++) {
            temp = temp.next;
        }
        System.out.println("倒数第" + index + "个节点：" + temp);
        return temp;

    }

    /**
     * 单链表的反转
     */
    public static void reversetList(HeroNode head) {
        //如果当前链表为空，或者只有一个节点，则无需反转
        if (head.next == null || head.next.next == null) {
            return;
        }

        //定义辅助变量，方便遍历
        HeroNode cur = head.next;
        //指向当前节点的下一个节点
        HeroNode next = null;
        //反转链表
        HeroNode reverseHead = new HeroNode(0, "", "");
        //遍历原来的链表，将原来的节点放在反转链表的前一个节点上
        while (cur != null) {
            //保存当前节点的下一个节点，以便后面使用
            next = cur.next;
            //将cur的下一个节点连接到reverseHead节点的前端
            cur.next = reverseHead.next;
            //将cur连接到新的反转链表
            reverseHead.next = cur;

            cur = next;
        }
        head.next = reverseHead.next;
    }

    /**
     * 4、从尾到头打印单链表,使用栈
     */
    public static void reversePrint(HeroNode heroNode) {
        if (heroNode.next == null) {
            return;
        }
        HeroNode temp = heroNode.next;
        Stack<HeroNode> heroNodeStack = new Stack<>();
        while (temp != null) {
            heroNodeStack.push(temp);
            temp = temp.next;
        }
        while (!heroNodeStack.isEmpty()) {
            System.out.println(heroNodeStack.pop()); //stack的特点是先进后出
        }
    }
}

/**
 * 定义 SingleLinkedList 管理我们的HeroNode
 */
class SingleLinkedList {

    //设置头结点
    HeroNode heroNode = new HeroNode(0, "", "");

    public HeroNode getHeroNode() {
        return heroNode;
    }

    /**
     * 添加节点到单向链表
     * 思路，当不考虑编号顺序时
     * 1. 找到当前链表的最后节点
     * 2. 将最后这个节点的 next 指向 新的节点
     */
    public void add(HeroNode node) {
        //因为 head 节点不能动，因此我们需要一个辅助遍历 temp
        HeroNode temp = heroNode;
        while (true) {
            //1. 找到当前链表的最后节点
            if (temp.next == null) {
                break;
            }
            //如果没有找到最后, 将将 temp 后移
            temp = temp.next;
        }
        //当退出 while 循环时，temp 就指向了链表的最后
        //将最后这个节点的 next 指向 新的节点
        temp.next = node;
    }

    /**
     * 根据序号添加节点到单链表--按顺序添加
     * 1、先找到要添加节点的前一个节点
     * 2、然后  新的节点.next = temp.next
     * temp.next = 新的节点
     */
    public void addByOrder(HeroNode node) {

        HeroNode temp = heroNode;

        //设置flag标识要添加的编号是否存在，默认为false
        boolean flag = false;
        while (true) {
            //表示temp已经在链表的结尾
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > node.no) {
                //表示temp的下一个节点的编号大于本节点，即找到了要添加节点的前一个节点
                break;
            } else if (temp.next.no == node.no) {
                //表示要添加的编号已经存在
                flag = true;
                break;
            }
            //下移
            temp = temp.next;
        }

        if (flag) {
            //不能添加，说明添加编号已存在
            System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
        } else {
            node.next = temp.next;
            temp.next = node;
        }
    }

    /**
     * 修改链表值内容
     * 找到节点位置，修改
     *
     * @param newHeroNode
     */
    public void update(HeroNode newHeroNode) {

        if (heroNode.next == null) {
            System.out.println("链表为空!");
            return;
        }

        HeroNode temp = heroNode.next;
        //设置flag标识要添加的编号是否找到，默认为false
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == newHeroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //为true表示已找到位置，可进行修改
            temp.nickname = newHeroNode.nickname;
            temp.name = newHeroNode.name;
        } else {
            //没有找到
            System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
        }

    }

    /**
     * 删除节点
     * 1、先找到删除节点的前一个节点
     * 2、temp.next = temp.next.next
     *
     * @param no 节点编号
     */
    public void deleteList(int no) {
        if (heroNode.next == null) {
            System.out.println("链表为空!");
            return;
        }

        HeroNode temp = heroNode;
        //flag标识表示是否找到节点，默认为false
        boolean flag = false;
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //表示已找到
            temp.next = temp.next.next;
        } else {
            System.out.printf("要删除的 %d 节点不存在\n", no);
        }

    }

    public void list() {

        if (heroNode.next == null) {
            System.out.println("链表为空!");
            return;
        }
        //因为 head 节点不能动，因此我们需要一个辅助遍历 temp
        HeroNode temp = heroNode.next;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }

    }

}


/**
 * 定义 HeroNode ， 每个 HeroNode 对象就是一个节点
 */
class HeroNode {
    public int no;
    public String name;
    public String nickname; //昵称
    public HeroNode next; //指向下一个节点

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}